class SortedDimensions {
  constructor() {
    this.dimensions = [];
  }

  binarySearch0(array, targetDimension) {
    const len = array.length;
    const { top, bottom } = targetDimension;
    let low = 0, high = len - 1, mid;
    const max = array[len - 1];

    if (!len) {
      return -1;
    }

    // 大部分场景是一边addRow一边mergeCells，merge的行是较大值，直接与max比较
    if (max && max.bottom < top) {
      return -(len + 1);
    }

    while (low <= high) {
      // Math.ceil((low + high) / 2)
      mid = (low + high) >>> 1;
      const { top: midTop, bottom: midBottom } = array[mid];

      if (midBottom < top) {
        // targetDimension > midVal
        low = mid + 1;
      } else if (midTop > bottom) {
        // targetDimension < midVal
        high = mid - 1;
      } else {
        // 重合
        return mid;
      }
    }

    // low = target应当插入的位置
    return -(low + 1);
  }

  // 如果交叉则返回交叉的Range对象
  findIntersection0(dimension) {
    const { left, right } = dimension;
    const insertionIndexes = [];
    for (let i = left; i <= right; i++) {
      const array = this.dimensions[i];
      if (array) {
        const index = this.binarySearch0(array, dimension);
        if (index >= 0) {
          return array[index];
        } else {
          const insertionIndex = -index - 1;
          const d = array[insertionIndex];
          if (d && d.intersects(dimension)) {
            return d;
          } else {
            insertionIndexes.push(insertionIndex);
          }
        }
      } else {
        this.dimensions[i] = [];
        insertionIndexes.push(0);
      }
    }

    return insertionIndexes;
  }

  findIntersection(dimension) {
    const d = this.findIntersection0(dimension);
    if (d.length) {
      return null;
    }
    return d;
  }

  // 如果交叉则返回交叉的Range对象；否则将新的Range插入并返回false
  findIntersectionOrAdd(dimension) {
    const merge = this.findIntersection0(dimension);
    const { left } = dimension;
    if (!merge.length) {
      // 返回冲突的Range对象
      return merge;
    } else {
      // merge没有冲突
      merge.forEach((iIndex, index) => {
        this.dimensions[index + left].splice(iIndex, 0, dimension);
      });
      return false;
    }
  }

  remove(topLeft) {
    const { left, right } = topLeft;
    let dimension;
    for (let i = left; i <= right; i++) {
      const col = this.dimensions[i];
      if (col) {
        const index = this.binarySearch0(col, topLeft);
        if (index >= 0) {
          dimension = col[index];
          col.splice(index, 1);
        }
      }
    }
    return dimension;
  }

  get right() {
    return this.dimensions.length;
  }

  get left() {
    const first = this.dimensions.findIndex(Boolean);
    return first < 0 ? 0 : first;
  }

}

module.exports = SortedDimensions;
